Welcome! This is ratel's Blog.

개발 스터디
- JavaScript
- algorithm
개발일지
Home

Contact

Copyright © 2024 | Yankos

Home > 개발 스터디 > algorithm

Now Loading ...

algorithm

Greedy Algorithm
그리디 알고리즘(탐욕법, Greedy Algorithm) WHAT IS? 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적으로 최적의 해답에 근사한 값을 찾는 알고리즘! 위 설명에서 알 수 있듯이 그리디 알고리즘은 그 자체로 항상 최적해를 보장해 주진 못한다. 그렇기 때문에 보통 스택과 같은 자료구조나 정렬 알고리즘과 짬뽕해서 사용하곤 한다. WHAT CONDITIONS? 그리디를 사용하기 위해서는 아래 두 조건을 만족하여야 적용할 수 있다. 탐욕 선택 속성(Greedy Choice Property) 앞의 선택이 이후의 선택에 영향을 주지 않는다. 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말함. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것임. 최적 부분 구조(Optimal Substructure) 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미함. HOW USE? 그리디 알고리즘은 아래 3단계를 걸쳐 적용될 수 있다. 선택 절차(Selection Procedure) ‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다. 적절성 검사(Feasibility Check) 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다. 해답 검사(Solution Check) 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다. 그리디 알고리즘의 대표적인 문제로 거스름돈 문제가 있습니다. ❓500원, 100원, 50원, 10원의 동전이 있을 때, 주어진 금액을 최소 개수의 동전으로 거슬러주려면 어떻게 해야 할까요? 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다. public int GreedyAlgorithm(int k) { int[] arr = new int[]{500, 100, 50, 10, 5, 1}; int answer = 0; for (int n : arr) { if (k > 0) { int temp = k / n; answer += temp; k -= (n * temp); }else break; } return answer; } DP와의 비교 핵심부터 말하자면 DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태이다. 분류 Greedy DP 설명 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 성립 조건 1. 탐욕 선택 속성(Greedy Choice Property)2. 최적 부분 구조(Optimal Substructure) 1. 중복 부분 문제 (Overlapping Subproblems)2.최적 부분 구조 (Optimal Substructure) 중복 부분 문제 중복 부분 문제를 해결하지 않습니다. 중복 부분 문제를 해결할 수 있습니다. 상황 - 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다- 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다. - 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다- 모든 상황을 계산하기에 시간이 오래 걸립니다. -end-
개발 스터디 · 2025-07-03
dynamic programming
동적 계획법(Dynamic Programming) WHAT IS? 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 컨셉! 수열의 점화식 느낌 유남생? aka ‘기억하며 풀기’ WHY USE? 사실 DP는 일반적인 재귀법과 매우 유사함. 하지만 그 효율성은 말도 못하게 더 높다. 일반적인 재귀법은 보통 O(n^2)의 시간 복잡도를 나타내는 반면 DP는 O(f(n))의 시간 복잡도를 보인다. 위 그림처럼 재귀법을 사용한다면 불필요하게 한번 구했던 값 (=함수 호출 횟수)을 한번 더 구해야함. 이때 한번 구한 작은 문제의 결과 를 저장했다가 재사용 하면 굉장히 효율적이게 되겠죵? 이것이 바로 DP의 핵심 개념입니다! WHAT CONDITIONS? DP를 사용하기 위해서는 아래 2조건을 만족해야 합니다. 겹치는 부분 문제 (Overlapping Subproblems) DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다. 즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다. 최적 부분 구조 (Optimal Substructure) 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다. HOW USE? 아래 단계를 거쳐 문제를 해결할 수 있습니다. DP로 풀 수 있는 문제인지 확인 문제의 변수 파악 변수 간 관계식 만들기(점화식) 메모하기(memoization or tabulation) 기저 상태 파악하기 구현하기 1. DP로 풀 수 있는 문제인지 확인 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단 보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다. 2. 문제의 변수 파악 문제 내 변수의 개수를 알아내야 한다. ( = state를 결정한다.) 예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다. 3. 변수 간 관계식(점화식) 만들기 변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하므로 우리는 이를 관계식으로 만들어 낼 수 있고 그 관계식을 점화식이라고 한다! 예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 4. 메모하기 변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다. 5. 기저 상태 파악하기 가장 작은 문제의 상태를 알아야 한다. 피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식 해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 6. 구현하기 2가지 방식으로 구현 가능함. Bottom-Up (Tabulation 방식) - 반복문 사용 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다. Top-Down (Memoization 방식) - 재귀 사용 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식 packge com.test; public class Fibonacci{ // DP 를 사용 시 작은 문제의 결과값을 저장하는 배열 // Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음) static int[] topDown_memo; static int[] bottomup_table; public static void main(String[] args){ int n = 30; topDown_memo = new int[n+1]; bottomup_table = new int[n+1]; long startTime = System.currentTimeMillis(); System.out.println(naiveRecursion(n)); long endTime = System.currentTimeMillis(); System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime)); System.out.println(); startTime = System.currentTimeMillis(); System.out.println(topDown(n)); endTime = System.currentTimeMillis(); System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime)); System.out.println(); startTime = System.currentTimeMillis(); System.out.println(bottomUp(n)); endTime = System.currentTimeMillis(); System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime)); } // 단순 재귀를 통해 Fibonacci를 구하는 경우 // 동일한 계산을 반복하여 비효율적으로 처리가 수행됨 public static int naiveRecursion(int n){ if(n <= 1){ return n; } return naiveRecursion(n-1) + naiveRecursion(n-2); } // DP Top-Down을 사용해 Fibonacci를 구하는 경우 public static int topDown(int n){ // 기저 상태 도달 시, 0, 1로 초기화 if(n < 2) return topDown_memo[n] = n; // 메모에 계산된 값이 있으면 바로 반환! if(topDown_memo[n] > 0) return topDown_memo[n]; // 재귀를 사용하고 있음! topDown_memo[n] = topDown(n-1) + topDown(n-2); return topDown_memo[n]; } // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우 public static int bottomUp(int n){ // 기저 상태의 경우 사전에 미리 저장 bottomup_table[0] = 0; bottomup_table[1] = 1; // 반복문을 사용하고 있음! for(int i=2; i<=n; i++){ // Table을 채워나감! bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2]; } return bottomup_table[n]; } } /* 결과 832040 일반 재귀 소요 시간 : 9 832040 Top-Down DP 소요 시간 : 0 832040 Bottom-Up DP 소요 시간 : 0 */
개발 스터디 · 2025-06-16

Touch background to close